package com.uyong.study.algorithm.sort;

/**
 * 归并排序O(nlogn),非原地O(n),稳定
 * 
 * @author gonggy
 * @since 2019-01-23
 */
public class MergeSort {

	/**
	 * 排序，不带哨兵版
	 * 
	 * @param data
	 */
	public void sortNoSentry(int[] data) {
		sortNoSentry(data, 0, data.length - 1);
	}

	/**
	 * 排序，带哨兵版
	 * 
	 * @param data
	 */
	public void sortWithSentry(int[] data) {
		sortWithSentry(data, 0, data.length - 1);
	}

	private void sortNoSentry(int[] data, int begin, int end) {
		if (begin >= end) {
			return;
		}
		int middle = begin + (end - begin) / 2;
		sortNoSentry(data, begin, middle);
		sortNoSentry(data, middle + 1, end);
		mergeNoSentry(data, begin, middle, end);
	}

	private void sortWithSentry(int[] data, int begin, int end) {
		if (begin >= end) {
			return;
		}
		int middle = begin + (end - begin) / 2;
		sortWithSentry(data, begin, middle);
		sortWithSentry(data, middle + 1, end);
		mergeWithSentry(data, begin, middle, end);
	}

	private void mergeNoSentry(int[] data, int begin, int middle, int end) {
		// 临时数组
		int[] copy = new int[end - begin + 1];
		int left = begin, right = middle + 1, index = 0;
		while (left <= middle && right <= end) {
			if (data[left] > data[right]) {
				copy[index++] = data[right++];
			} else {
				copy[index++] = data[left++];
			}
		}
		// 判断哪边的数组有剩余的数据
		int remainBegin = left, remainEnd = middle;
		if (right <= end) {
			remainBegin = right;
			remainEnd = end;
		}
		// 将剩余的数据复制到临时数组中
		while (remainBegin <= remainEnd) {
			copy[index++] = data[remainBegin++];
		}
		// 将临时数组拷贝回原数组中
		for (int i = 0; i < copy.length; i++) {
			data[begin + i] = copy[i];
		}
	}

	private void mergeWithSentry(int[] data, int begin, int middle, int end) {
		int leftLength = middle - begin + 1;
		int rightLength = end - middle;
		int[] left = new int[leftLength + 1]; // +1是让最后一个当哨兵，下同
		int[] right = new int[rightLength + 1];

		System.arraycopy(data, begin, left, 0, leftLength);
		System.arraycopy(data, middle + 1, right, 0, rightLength);

		left[leftLength] = Integer.MAX_VALUE; // 将哨兵设置为最大值，下同
		right[rightLength] = Integer.MAX_VALUE;

		int leftIndex = 0, rightIndex = 0;
		for (int i = begin; i <= end; i++) {
			if (left[leftIndex] <= right[rightIndex]) {
				data[i] = left[leftIndex++];
			} else {
				data[i] = right[rightIndex++];
			}
		}
	}

}
